Search for: All records

Many important science and engineering problems can be converted into NP-complete problems which are of significant importance in computer science and mathematics. Currently, neither existing classical nor quantum algorithms can solve these problems in polynomial time. To address this difficulty, this paper proposes a quantum feasibility labeling (QFL) algorithm to label all possible solutions to the vertex coloring problem, which is a well-known NP-complete problem. The QFL algorithm converts the vertex coloring problem into the problem of searching an unstructured database where good and bad elements are labeled. The recently proposed variational quantum search (VQS) algorithm was demonstrated to achieve an exponential speedup, in circuit depth, up to 26 qubits in finding good element(s) from an unstructured database. Using the labels and the associated possible solutions as input, the VQS can find all feasible solutions to the vertex coloring problem. The number of qubits and the circuit depth required by the QFL each is a polynomial function of the number of vertices, the number of edges, and the number of colors of a vertex coloring problem. We have implemented the QFL on an IBM Qiskit simulator to solve a 4-colorable 4-vertex 3-edge coloring problem. 

Grover’s search algorithm (GSA) offers quadratic speedup in searching unstructured databases but suffers from exponential circuit depth complexity. Here, we present two quantum circuits called HX and Ry layers for the searching problem. Remarkably, both circuits maintain a fixed circuit depth of two and one, respectively, irrespective of the number of qubits used. When the target element’s position index is known, we prove that either circuit, combined with a single multi-controlled X gate, effectively amplifies the target element’s probability to over 0.99 for any qubit number greater than seven. To search unknown databases, we use the depth-1 Ry layer as the ansatz in the Variational Quantum Search (VQS), whose efficacy is validated through numerical experiments on databases with up to 26 qubits. The VQS with the Ry layer exhibits an exponential advantage, in circuit depth, over the GSA for databases of up to 26 qubits. 

Abstract Three cross-incompatibility loci each control a distinct reproductive barrier in both domesticated maize (Zea mays ssp. mays) and its wild teosinte relatives. These 3 loci, Teosinte crossing barrier1 (Tcb1), Gametophytic factor1 (Ga1), and Ga2, each play a key role in preventing hybridization between incompatible populations and are proposed to maintain the barrier between domesticated and wild subspecies. Each locus encodes both a silk-active and a matching pollen-active pectin methylesterase (PMEs). To investigate the diversity and molecular evolution of these gametophytic factor loci, we identified existing and improved models of the responsible genes in a new genome assembly of maize line P8860 that contains active versions of all 3 loci. We then examined 52 assembled genomes from 17 species to classify haplotype diversity and identify sites under diversifying selection during the evolution of these genes. We show that Ga2, the oldest of these 3 loci, was duplicated to form Ga1 at least 12 million years ago. Tcb1, the youngest locus, arose as a duplicate of Ga1 before or around the time of diversification of the Zea genus. We find evidence of positive selection during evolution of the functional genes at an active site in the pollen-expressed PME and predicted surface sites in both the silk- and pollen-expressed PMEs. The most common allele at the Ga1 locus is a conserved ga1 allele (ga1-Off), which is specific haplotype containing 3 full-length PME gene copies, all of which are noncoding due to conserved stop codons and are between 610 thousand and 1.5 million years old. We show that the ga1-Off allele is associated with and likely generates 24-nt siRNAs in developing pollen-producing tissue, and these siRNAs map to functional Ga1 alleles. In previously published crosses, the ga1-Off allele was associated with reduced function of the typically dominant functional alleles for the Ga1 and Tcb1 barriers. Taken together, this seems to be an example of an allele at a reproductive barrier locus being associated with an as yet undetermined mechanism capable of silencing the reproductive barrier. 

Three cross-incompatibility loci each control a distinct reproductive barrier in both domesticated maize (Zea mays ssp. mays) and its wild teosinte relatives. These three loci, Teosinte crossing barrier1 (Tcb1), Gametophytic factor1 (Ga1), and Ga2, each play a key role in preventing hybridization between incompatible populations and are proposed to maintain the barrier between domesticated and wild subspecies. Each locus encodes both a silk-active and a matching pollen-active pectin methylesterase (PMEs). To investigate the diversity and molecular evolution of these gametophytic factor loci, we identified existing and improved models of the responsible genes in a new genome assembly of maize line P8860 that contains active versions of all three loci. We then examined fifty-two assembled genomes from seventeen species to classify haplotype diversity and identify sites under diversifying selection during the evolution of these genes. We show that Ga2, the oldest of these three loci, was duplicated to form Ga1 at least 12 million years ago. Tcb1, the youngest locus, arose as a duplicate of Ga1 before or around the time of diversification of the Zea genus. We find evidence of positive selection during evolution of the functional genes at an active site in the pollen-expressed PME and predicted surface sites in both the silk- and pollen-expressed PMEs. The most common allele at the Ga1 locus is a conserved ga1 allele (ga1-Off), which is a specific haplotype containing three full-length PME gene copies, all of which are non-coding due to conserved stop codons and are between 610 thousand and 1.5 million years old. We show that the ga1-Off allele is associated with and likely generates 24-nt siRNAs in developing pollen-producing tissue, and these siRNAs map to functional Ga1 alleles. In previously-published crosses, the ga1-Off allele was associated with reduced function of the typically dominant functional alleles for the Ga1 and Tcb1 barriers. Taken together, this seems to be an example of a type of epigenetic trans-homolog silencing known as paramutation, functioning at a locus controlling a reproductive barrier. 

Simulating quantum circuits using classical computers can accelerate the development and validation of quantum algorithms. Our newly developed algorithm, variational quantum search (VQS), has shown an exponential advantage over Grover's algorithm in the range from 5 to 26 qubits, in terms of circuit depth, for searching unstructured databases. We need to further validate the VQS for more than 26 qubits. Numerous simulators have been developed. However, it is not clear which simulator is most suitable for executing VQS with many qubits. To solve this issue, we implement a typical quantum circuit used in VQS on eight mainstream simulators. Results show that the time and memory required by most simulators increase exponentially with the number of qubits and that Pennylane with GPU and Qulacs are the most suitable simulators for executing VQS efficiently. Our results aid researchers in selecting suitable quantum simulators without the need for exhaustive implementation, and we have made our codes available for community contributions. 

Reproductive phasiRNAs (phased, small interfering RNAs) are broadly present in angiosperms and play crucial roles in sustaining male fertility. While the premeiotic 21-nt (nucleotides) phasiRNAs and meiotic 24-nt phasiRNA pathways have been extensively studied in maize (Zea mays) and rice (Oryza sativa), a third putative category of reproductive phasiRNAs–named premeiotic 24-nt phasiRNAs–have recently been reported in barley (Hordeum vulgare) and wheat (Triticum aestivum). To determine whether premeiotic 24-nt phasiRNAs are also present in maize and related species and begin to characterize their biogenesis and function, we performed a comparative transcriptome and degradome analysis of premeiotic and meiotic anthers from five maize inbred lines and three teosinte species/subspecies. Our data indicate that a substantial subset of the 24-nt phasiRNA loci in maize and teosinte are already highly expressed at the premeiotic phase. The premeiotic 24-nt phasiRNAs are similar to meiotic 24-nt phasiRNAs in genomic origin and dependence on DCL5 (Dicer-like 5) for biogenesis, however, premeiotic 24-nt phasiRNAs are unique in that they are likely i) not triggered by microRNAs, ii) not loaded by AGO18 proteins, and iii) not capable of mediatingPHASprecursor cleavage. In addition, we also observed a group of premeiotic 24-nt phasiRNAs in rice using previously published data. Together, our results indicate that the premeiotic 24-nt phasiRNAs constitute a unique class of reproductive phasiRNAs and are present more broadly in the grass family (Poaceae) than previously known. 

Plant cells accumulate small RNA molecules that regulate plant development, genome stability, and environmental responses. These small RNAs fall into three major classes based on their function and mechanisms of biogenesis—microRNAs, heterochromatic small interfering RNAs, and secondary small interfering RNAs—plus several other less well-characterized categories. Biogenesis of each small RNA class requires a pathway of factors, some specific to each pathway and others involved in multiple pathways. Diverse sequenced plant genomes, along with rapid developments in sequencing, imaging, and genetic transformation techniques, have enabled significant progress in understanding the biogenesis, functions, and evolution of plant small RNAs, including those that had been poorly characterized because they were absent or had low representation in Arabidopsis ( Arabidopsis thaliana). Here, we review recent findings about plant small RNAs and discuss our current understanding of their biogenesis mechanisms, targets, modes of action, mobility, and functions in Arabidopsis and other plant species, including economically important crops. Expected final online publication date for the Annual Review of Plant Biology, Volume 74 is May 2023. Please see http://www.annualreviews.org/page/journal/pubdates for revised estimates. 

Abstract Several protein families participate in the biogenesis and function of small RNAs (sRNAs) in plants. Those with primary roles include Dicer-like (DCL), RNA-dependent RNA polymerase (RDR), and Argonaute (AGO) proteins. Protein families such as double-stranded RNA-binding (DRB), SERRATE (SE), and SUPPRESSION OF SILENCING 3 (SGS3) act as partners of DCL or RDR proteins. Here, we present curated annotations and phylogenetic analyses of seven sRNA pathway protein families performed on 196 species in the Viridiplantae (aka green plants) lineage. Our results suggest that the RDR3 proteins emerged earlier than RDR1/2/6. RDR6 is found in filamentous green algae and all land plants, suggesting that the evolution of RDR6 proteins coincides with the evolution of phased small interfering RNAs (siRNAs). We traced the origin of the 24-nt reproductive phased siRNA-associated DCL5 protein back to the American sweet flag (Acorus americanus), the earliest diverged, extant monocot species. Our analyses of AGOs identified multiple duplication events of AGO genes that were lost, retained, or further duplicated in subgroups, indicating that the evolution of AGOs is complex in monocots. The results also refine the evolution of several clades of AGO proteins, such as AGO4, AGO6, AGO17, and AGO18. Analyses of nuclear localization signal sequences and catalytic triads of AGO proteins shed light on the regulatory roles of diverse AGOs. Collectively, this work generates a curated and evolutionarily coherent annotation for gene families involved in plant sRNA biogenesis/function and provides insights into the evolution of major sRNA pathways. 

Abstract NAKED ENDOSPERM1 (NKD1), NKD2, and OPAQUE2 (O2) are transcription factors important for cell patterning and nutrient storage in maize (Zea mays) endosperm. To study the complex regulatory interrelationships among these 3 factors in coregulating gene networks, we developed a set of nkd1, nkd2, and o2 homozygous lines, including all combinations of mutant and wild-type genes. Among the 8 genotypes tested, we observed diverse phenotypes and gene interactions affecting cell patterning, starch content, and storage proteins. From ∼8 to ∼16 d after pollination, maize endosperm undergoes a transition from cellular development to nutrient accumulation for grain filling. Gene network analysis showed that NKD1, NKD2, and O2 dynamically regulate a hierarchical gene network during this period, directing cellular development early and then transitioning to constrain cellular development while promoting the biosynthesis and storage of starch, proteins, and lipids. Genetic interactions regulating this network are also dynamic. The assay for transposase-accessible chromatin using sequencing (ATAC-seq) showed that O2 influences the global regulatory landscape, decreasing NKD1 and NKD2 target site accessibility, while NKD1 and NKD2 increase O2 target site accessibility. In summary, interactions of NKD1, NKD2, and O2 dynamically affect the hierarchical gene network and regulatory landscape during the transition from cellular development to grain filling in maize endosperm. 

Abstract Plant small RNAs are important regulatory elements that fine-tune gene expression and maintain genome integrity by silencing transposons. Reproductive organs of monocots produce abundant phased, small interfering RNAs (phasiRNAs). The 21-nt reproductive phasiRNAs triggered by miR2118 are highly enriched in pre-meiotic anthers, and have been found in multiple eudicot species, in contrast with prior reports of monocot specificity. The 24-nt reproductive phasiRNAs are triggered by miR2275, and are highly enriched during meiosis in many angiosperms. Here, we report the widespread presence of the 21-nt reproductive phasiRNA pathway in eudicots including canonical and non-canonical microRNA (miRNA) triggers of this pathway. In eudicots, these 21-nt phasiRNAs are enriched in pre-meiotic stages, a spatiotemporal distribution consistent with that of monocots and suggesting a role in anther development. Although this pathway is apparently absent in well-studied eudicot families including the Brassicaceae, Solanaceae and Fabaceae, our work in eudicots supports an earlier singular finding in spruce, a gymnosperm, indicating that the pathway of 21-nt reproductive phasiRNAs emerged in seed plants and was lost in some lineages.